package org.lintcode_Pattern;

/**
 * @Auther: qingle
 * @Date: 2024/8/20-22:31
 * @Description:
 * 使用条件
 * • 排序数组 (30-40%是二分)
 * • 当面试官要求你找一个比 O(n) 更小的时间复杂度算法的时候(99%)
 * • 找到数组中的一个分割位置，使得左半部分满足某个条件，右半部分不满足(100%)
 * • 找到一个最大/最小的值使得某个条件被满足(90%)
 * 复杂度
 * • 时间复杂度：O(logn)
 * • 空间复杂度：O(1)
 *
 *
 * 炼码例题
 * • LintCode 14. 二分查找(在排序的数据集上进行二分)
 * • LintCode 460. 在排序数组中找最接近的 K 个数 (在未排序的数据集上进行二分)
 * • LintCode 437. 书籍复印(在答案集上进行二分 )
 * @version: 1.0
 */
public class A1二分法 {


	public static void main(String[] args) {


	}

	/**
	 * 其基本思想是将目标值与数组中间的元素进行比较，如果目标值等于中间元素，则查找成功；
	 * 如果目标值小于中间元素，则在数组左半部分进行查找；
	 * 如果目标值大于中间元素，则在数组右半部分进行查找。这个过程将重复，直到找到目标值或查找范围为空。
	 * @param nums
	 * @param target
	 * @return
	 */
	public int binarySearch(int[] nums, int target) {
		if (nums == null || nums.length == 0) {
			return -1;
		}

		int start = 0, end = nums.length - 1;

		while (start < end) {
			int mid = start + (end - start) / 2;
			if (nums[mid] == target) {
				return mid;
			} else if (nums[mid] < target) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}

		if (nums[start] == target) {
			return start;
		}

		return -1;
	}


	public int binarySearchNote(int[] nums, int target) {
		// corner case 处理
		if (nums == null || nums.length == 0) {
			return -1;
		}

		int start = 0, end = nums.length - 1;

		// 要点 1: start + 1 < end 可以保证循环正常进行
		while (start < end) {
			// 要点 2：使用 start + (end - start) / 2 来避免溢出
			int mid = start + (end - start) / 2;

			// 要点 3：=, <, > 分开讨论，mid 不 +1 也不 -1
			if (nums[mid] == target) {
				return mid; // 找到目标值，返回索引
			} else if (nums[mid] < target) {
				start = mid + 1; // 调整搜索范围到右半部分
			} else {
				end = mid - 1; // 调整搜索范围到左半部分
			}
		}

		// 要点 4: 循环结束后，单独处理 start 和 end
		if (nums[start] == target) {
			return start; // 如果 start 处的值是目标值，返回 start
		}
		// end 已经在循环中被更新，如果需要单独检查 end，可以取消下面两行的注释
		// if (nums[end] == target) {
		//     return end; // 如果 end 处的值是目标值，返回 end
		// }

		return -1; // 如果没有找到目标值，返回 -1
	}
}
